home *** CD-ROM | disk | FTP | other *** search
/ Amiga Packmags / NewsFlash - Issue 19 (1991-08)(UGA - NewsFlash UK)(Disk 1 of 2).zip / NewsFlash - Issue 19 (1991-08)(UGA - NewsFlash UK)(Disk 1 of 2).adf / sources / bitsort.asm.pp / bitsort.asm
Assembly Source File  |  1978-01-06  |  3KB  |  149 lines
  1. *************************************
  2. *                                   *
  3. * BitSort.asm                       *
  4. *                                   *
  5. * Written by Nico François          *
  6. * Public Domain                     *
  7. *************************************
  8.  
  9.     SECTION "bitsort",CODE
  10.  
  11. *
  12. * This function will sort a table or array of longwords from low to high.
  13. *
  14. * It is very fast (6 times faster than the SAS/C quicksort function!) and
  15. * very easy to use.
  16. * This function is recursive, but will never use more than 800 bytes of
  17. * stackspace!!
  18. *
  19. *
  20. * C example:
  21. *
  22. * ULONG nums[20];
  23. *
  24. * main()
  25. * {
  26. *    ...
  27. *    /* fill 'nums' array with numbers */
  28. *    ...
  29. *    /* Sort the array */
  30. *    BitSortLongs (nums, 20);
  31. *    ...
  32. * }
  33. *
  34. *
  35. * Assembly example:
  36. *
  37. *    SECTION "sort",CODE
  38. *
  39. * start:
  40. *    ...                       ; fill array with numbers
  41. *    lea    nums,a0
  42. *    moveq  #20,d0
  43. *    jsr    BitSortLongs(PC)   ; sort the array
  44. *    ...
  45. *
  46. *    SECTION "array",DATA
  47. *
  48. * nums:
  49. *    ds.l   20
  50. *
  51.  
  52.     XDEF _BitSortLongs
  53.     XDEF @BitSortLongs
  54.  
  55. * void BitSortLongs (ULONG *table, ULONG num);
  56. *                    A0            D0
  57. _BitSortLongs:             ; normal C entry point
  58.    move.l   4(a7),a0
  59.    move.l   8(a7),d0
  60. @BitSortLongs:             ; __regargs entry point
  61. BitSortLongs:              ; assembly entry point
  62.    move.l   d2,-(a7)
  63.    move.l   d0,d1
  64.    move.l   a0,a1
  65.  
  66.    moveq    #0,d2
  67.    subq.w   #1,d0
  68. looplongest:
  69.    cmp.l    (a0)+,d2
  70.    bcc.b    nonewlargest
  71.    move.l   -4(a0),d2
  72. nonewlargest:
  73.    dbra     d0,looplongest
  74.    tst.l    d2
  75.    beq.s    allsorted
  76.  
  77.    moveq    #32,d0
  78. loopfindbit:
  79.    subq.l   #1,d0
  80.    btst     d0,d2
  81.    beq.s    loopfindbit
  82.  
  83.    lsl.l    #2,d1
  84.    move.l   a1,a0
  85.    add.l    d1,a0
  86.    move.l   d0,-(a7)
  87.    move.l   a0,-(a7)
  88.    move.l   a1,-(a7)
  89.    bsr.b    sortbits
  90.    lea      12(a7),a7
  91.  
  92. allsorted:
  93.    move.l   (a7)+,d2
  94.    rts
  95.  
  96.  
  97. sortbits:
  98.    movem.l  a0/d2,-(a7)
  99.    move.l   12(a7),a0      ; table
  100.    move.l   16(a7),a1      ; pointer after end of table
  101.    move.l   20(a7),d2      ; bit number to test
  102.    move.l   a1,d0
  103.    subq.l   #4,d0
  104.    cmp.l    d0,a0
  105.    bcc.b    tablesorted
  106.    bra.b    startfind1bit
  107.  
  108. find1bit:
  109.    addq.l   #4,a0
  110. startfind1bit:
  111.    cmp.l    a1,a0
  112.    bcc.b    allpassed
  113.    move.l   (a0),d0
  114.    btst     d2,d0
  115.    beq.b    find1bit
  116.  
  117. bitis1:
  118.    move.l   -(a1),d0
  119.    btst     d2,d0
  120.    beq.b    bitis0
  121.    cmp.l    a1,a0
  122.    bcc.b    allpassed
  123.    bra.b    bitis1
  124. bitis0:
  125.    move.l   (a0),(a1)
  126.    move.l   d0,(a0)
  127.    bra.b    find1bit
  128.  
  129. allpassed:
  130.    subq.l   #1,d2
  131.    bcs.b    tablesorted
  132.  
  133.    move.l   d2,-(a7)      ; push bit number
  134.    move.l   a0,-(a7)
  135.    move.l   8+12(a7),-(a7)
  136.    bsr.b    sortbits
  137.    lea      12(a7),a7
  138.    move.l   d2,-(a7)      ; push bit number
  139.    move.l   4+16(a7),-(a7)
  140.    move.l   a0,-(a7)
  141.    bsr.b    sortbits
  142.    lea      12(a7),a7
  143.  
  144. tablesorted:
  145.    movem.l  (a7)+,a0/d2
  146.    rts
  147.  
  148.    END
  149.